package com.fyl.basic_algorithm.ShortestPath;

import java.util.Arrays;
import java.util.LinkedList;

import static java.util.Collections.swap;

/**
 * @Description:
 * @author:fyl
 * @date 2021/4/19 15:26
 * @Modified By:
 * @Modified Date:
 */
public class Graph {
    private LinkedList<Edge> adj[];
    private int v;

    public Graph(LinkedList<Edge>[] adj, int v) {
        this.v = v;
        for (int i = 0; i < v; i++) {
            this.adj[i] = new LinkedList<>();
        }
    }

    //添加一条边
    public void addEdge(int s, int t, int w) {
        this.adj[s].add(new Edge(s, t, w));
    }

    private class Edge {
        private int sid; //边的起始顶点编号
        private int tid; //边的终止顶点编号
        private int w;  //权重

        public Edge(int sid, int tid, int w) {
            this.sid = sid;
            this.tid = tid;
            this.w = w;
        }
    }

    //为了dijkstra实现用的
    private class Vertex {
        public int id;  //顶点编号id
        public int dist; //从起始顶点到这个顶点的距离

        public Vertex(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
    }

    /**
     * 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
     * 根据vertex.dist构建小顶堆
     */
    private class PriorityQueue {
        private Vertex[] nodes;
        private int n;  //队列中可以储存的最大数据个数
        private int count;  //队列中已经储存的数据个数

        public PriorityQueue(int v) {
            this.nodes = new Vertex[v + 1];
            this.n = v;
            this.count = 0;
        }

        public Vertex poll() {

            return null;
        }

        public void add(Vertex vertex) {
            if (count == n) return; //队列满了
            ++count;
            nodes[count] = vertex;
            int i = count;
            while (i / 2 > 0 && nodes[i].dist < nodes[i / 2].dist) {
                swap(Arrays.asList(nodes), i, i / 2);
                i = i / 2;
            }
        }

        public void update(Vertex vertex) {
            while (true){
                int minPos = count;

            }
        }

        public boolean isEmpty() {
            return count == 0;
        }
    }

    /**
     * 从顶点s到t的最短路径
     *
     * @param s 起点
     * @param t 终点
     */
    public void dijkstra(int s, int t) {
        int[] predecessor = new int[this.v]; //用来还原最短路径
        Vertex[] vertexes = new Vertex[this.v];
        for (int i = 0; i < this.v; i++) {
            vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
        }

        PriorityQueue queue = new PriorityQueue(this.v); //小顶堆
        boolean[] inqueue = new boolean[this.v]; //标记是否进入过小顶堆
        vertexes[s].dist = 0;
        queue.add(vertexes[s]);
        inqueue[s] = true;
        while (!queue.isEmpty()) {
            Vertex minVertex = queue.poll();  //取堆顶元素并删除
            if (minVertex.id == t) break;  //最短路径产生了
            for (int i = 0; i < adj[minVertex.id].size(); i++) {
                Edge e = adj[minVertex.id].get(i);  //取出一条minVetex相连的边
                Vertex nextVertex = vertexes[e.tid]; //minVertex --> nextVertex
                if (minVertex.dist + e.w < nextVertex.dist) {  //更新next的dist
                    nextVertex.dist = minVertex.dist + e.w;
                    predecessor[nextVertex.id] = minVertex.id;
                    if (inqueue[nextVertex.id]) {
                        queue.update(nextVertex);  //更新队列中的dist值
                    } else {
                        queue.add(nextVertex);
                        inqueue[nextVertex.id] = true;
                    }
                }
            }
        }
        //输出最短路径
        System.out.print(s);
        print(s, t, predecessor);
    }

    private void print(int s, int t, int[] predecessor) {
        if (s == t) return;
        print(s, predecessor[t], predecessor);
        System.out.println("->" + t);
    }
}
